# LeetCode 239、滑动窗口最大值
# 一、题目描述
给定一个数组 nums 和滑动窗口的大小 k,请找出所有滑动窗口里的最大值。
示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
提示:
- 你可以假设
k
总是有效的,在输入数组不为空的情况下,1 ≤ k ≤ 输入数组的大小。
# 二、题目解析
滑动窗口这个词包含两个概念,一个是滑动,一个是窗口。
首先是窗口需要生成,一开始里面是没有任何元素的。
然后再滑动,随着窗口不断的滑动,窗口里面的元素个数从 0 到 1,再到 2,再到 3,此时,从窗口里面宣传最大值。
想要找出当前窗口里面的最大值,自然而然的想法就是遍历窗口中的所有元素,从中选出最大值,这样的复杂度是 O(k*n)
级别,复杂度有点高。
首先滑动窗口滑过所有的元素必然要经历 O(n)
的时间,这没法调整,所以可以优化的方向在于获取当前窗口的最大值,即想办法从 O(k)
优化到 O(logk)
或者直接优化到 O(1)
。
使用双端队列!
让窗口移动的过程,维护好队列里面的元素,做到每次窗口移动后都能马上知道当前窗口的最大值,由于想要做到 O(1) 的级别拿到最大值,那么必须是它的队首始终是最大值,也就是说我们需要维护一个递减队列用来保存队列中 所有递减的元素 。
一开始,窗口中只有 1,队列中放入 1。
窗口滑动,包含了 1 和 3,3 大于 1,如果直接放入队列,队列为 1 3,不是递减队列,所以需要先将 1 移除再放入 3 。
继续滑动,窗口元素为 1 3 -1 。
滑动窗口已经有三个元素,是合格的窗口,获取它的最大值只需要获取队列的队首元素就行。
同样的,窗口不断的向右移动,每次窗口都会增加新的元素,为了让队列中的队首元素始终是当前窗口的最大值,需要把队列中所有小于新元素值的那些元素移除。
# 三、参考代码
# 1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 滑动窗口最大值( LeetCode 239 ):https://leetcode-cn.com/problems/sliding-window-maximum/
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
// 边界情况
if(nums.length == 0 || k == 0){
return new int[0];
}
// 构建双端队列
Deque<Integer> deque = new LinkedList<>();
// 构建存储最大值的数组
int[] res = new int[nums.length - k + 1];
// 一开始滑动窗口不包含 K 个元素,不是合格的滑动窗口
for(int i = 0; i < k; i++) {
// 在滑动过程中,维护好 deque,确保它是单调递减队列
// 反复判断,如果队列不为空且当前考察元素大于等于队尾元素,则将队尾元素移除。
// 直到考察元素可以放入到队列中
while(!deque.isEmpty() && deque.peekLast() < nums[i]){
deque.removeLast();
}
// 考察元素可以放入到队列中
deque.addLast(nums[i]);
}
// 这个时候,滑动窗口刚刚好有 k 个元素,是合格的滑动窗口,那么最大值就是队列中的队首元素
res[0] = deque.peekFirst();
// 现在让滑动窗口滑动
for(int i = k; i < nums.length; i++) {
// 滑动窗口已经装满了元素,向右移动会把窗口最左边的元素抛弃
// i - k 为滑动窗口的最左边
// 如果队列的队首元素和窗口最左边的元素相等,需要将队首元素抛出
// 如果不写这个判断,会导致队列中会包含非当前窗口的元素
// 比如窗口大小为 1,队列为 1 -1,此时窗口为 【 1 】,队列为 1,输出最大值 1,下一个窗口为 【 -1 】,准备移动的时候队列 1 和数组最左端元素一样,必须移除,否则队列中是 【 1,-1 】,输出的结果是 1,而 1 不在窗口 【 -1 】中
if(deque.peekFirst() == nums[i - k]){
deque.removeFirst();
}
// 反复判断,如果队列不为空且当前考察元素大于等于队尾元素,则将队尾元素移除。
// 直到考察元素可以放入到队列中
while(!deque.isEmpty() && deque.peekLast() < nums[i]){
deque.removeLast();
}
// 考察元素可以放入到队列中
deque.addLast(nums[i]);
// 此时,结果数组的值就是队列的队首元素
res[i - k + 1] = deque.peekFirst();
}
// 最后返回 res
return res;
}
}
# **2、**C++ 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 滑动窗口最大值( LeetCode 239 ):https://leetcode-cn.com/problems/sliding-window-maximum/
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
// 构建存储最大值的数组
vector<int> res;
if(nums.size() == 0 || k == 0){
return res;
}
// 构建双端队列
deque<int> deque;
// 一开始滑动窗口不包含 K 个元素,不是合格的滑动窗口
for(int i = 0; i < k; i++) {
// 在滑动过程中,维护好 deque,确保它是单调递减队列
// 反复判断,如果队列不为空且当前考察元素大于等于队尾元素,则将队尾元素移除。
// 直到考察元素可以放入到队列中
while(!deque.empty() && deque.back() < nums[i]){
deque.pop_back();
}
// 考察元素可以放入到队列中
deque.push_back(nums[i]);
}
// 这个时候,滑动窗口刚刚好有 k 个元素,是合格的滑动窗口,那么最大值就是队列中的队首元素
res.push_back(deque.front());
// 现在让滑动窗口滑动
for(int i = k; i < nums.size(); i++) {
// 滑动窗口已经装满了元素,向右移动会把窗口最左边的元素抛弃
// i - k 为滑动窗口的最左边
// 如果队列的队首元素和窗口最左边的元素相等,需要将队首元素抛出
// 如果不写这个判断,会导致队列中会包含非当前窗口的元素
// 比如窗口大小为 1,队列为 1 -1,此时窗口为 【 1 】,队列为 1,输出最大值 1,下一个窗口为 【 -1 】,准备移动的时候队列 1 和数组最左端元素一样,必须移除,否则队列中是 【 1,-1 】,输出的结果是 1,而 1 不在窗口 【 -1 】中
if(deque.front() == nums[i - k]){
deque.pop_front();
}
// 反复判断,如果队列不为空且当前考察元素大于等于队尾元素,则将队尾元素移除。
// 直到考察元素可以放入到队列中
while(!deque.empty() && deque.back() < nums[i]){
deque.pop_back();
}
// 考察元素可以放入到队列中
deque.push_back(nums[i]);
// 此时,结果数组的值就是队列的队首元素
res.push_back(deque.front());
}
// 最后返回 res
return res;
}
};
# 3、Python 代码 1
登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者:程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 滑动窗口最大值( LeetCode 239 ):https://leetcode-cn.com/problems/sliding-window-maximum/
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
# 获取数组长度
n = len(nums)
# 构建双端队列
q = collections.deque()
# 建存储最大值的数组
res = []
# 边界情况
if k < 1:
return res
# 一开始滑动窗口不包含 K 个元素,不是合格的滑动窗口
for i in range (k):
# 在滑动过程中,维护好 deque,确保它是单调递减队列
# 反复判断,如果队列不为空且当前考察元素大于等于队尾元素,则将队尾元素移除。
# 直到考察元素可以放入到队列中
while q and q[-1] < nums[i]:
q.pop()
# 考察元素可以放入到队列中
q.append(nums[i])
# 这个时候,滑动窗口刚刚好有 k 个元素,是合格的滑动窗口,那么最大值就是队列中的队首元素
res.append(q[0])
# 现在让滑动窗口滑动
for i in range (k, n):
# 滑动窗口已经装满了元素,向右移动会把窗口最左边的元素抛弃
# i - k 为滑动窗口的最左边
# 如果队列的队首元素和窗口最左边的元素相等,需要将队首元素抛出
# 如果不写这个判断,会导致队列中会包含非当前窗口的元素
# 比如窗口大小为 1,队列为 1 -1,此时窗口为 【 1 】,队列为 1,输出最大值 1,下一个窗口为 【 -1 】,准备移动的时候队列 1 和数组最左端元素一样,必须移除,否则队列中是 【 1,-1 】,输出的结果是 1,而 1 不在窗口 【 -1 】中
# while q and nums[q[-1]] <= nums[i]:
# q.pop()
if q[0] == nums[i-k]:
q.popleft()
# 反复判断,如果队列不为空且当前考察元素大于等于队尾元素,则将队尾元素移除。
# 直到考察元素可以放入到队列中
while q and q[-1] < nums[i]:
q.pop()
q.append(nums[i])
# 考察元素可以放入到队列中
res.append(q[0])
# 最后返回 res
return res
# 3、Python 代码 2
添加索引的方式
登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者:程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 滑动窗口最大值( LeetCode 239 ):https://leetcode-cn.com/problems/sliding-window-maximum/
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
# 获取数组长度
n = len(nums)
# 构建双端队列,存储的是 nums 数组中元素的下标
q = collections.deque()
# 建存储最大值的数组
res = []
# 边界情况
if k < 1:
return res
# 一开始滑动窗口不包含 K 个元素,不是合格的滑动窗口
for i in range (k):
# 在滑动过程中,维护好 deque,确保它是单调递减队列
# 反复判断,如果队列不为空且当前考察元素大于等于队尾元素,则将队尾元素移除。
# 直到考察元素可以放入到队列中
# q[-1] 表示队尾元素下标,nums[q[-1]] 则是获取这个下标的元素
while q and nums[i] >= nums[q[-1]] :
q.pop()
# 考察元素的下标可以放入到队列中
q.append(i)
# 这个时候,滑动窗口刚刚好有 k 个元素,是合格的滑动窗口,那么最大值就是队列中的队首元素
# q[-1] 表示队首元素下标,nums[q[0]] 则是获取这个下标的元素
res.append(nums[q[0]])
# 现在让滑动窗口滑动
for i in range (k, n):
# 滑动窗口已经装满了元素,向右移动会把窗口最左边的元素抛弃
# i - k 为滑动窗口的最左边
# 如果队列的队首元素和窗口最左边的元素相等,需要将队首元素抛出
# 如果不写这个判断,会导致队列中会包含非当前窗口的元素
# 比如窗口大小为 1,队列为 1 -1,此时窗口为 【 1 】,队列为 1,输出最大值 1,下一个窗口为 【 -1 】,准备移动的时候队列 1 和数组最左端元素一样,必须移除,否则队列中是 【 1,-1 】,输出的结果是 1,而 1 不在窗口 【 -1 】中
# q 存储的是下标
while q and q[0] <= i-k:
q.popleft()
# 反复判断,如果队列不为空且当前考察元素大于等于队尾元素,则将队尾元素移除。
# 直到考察元素可以放入到队列中
while q and nums[q[-1]] <= nums[i]:
q.pop()
q.append(i)
# 考察元素可以放入到队列中
res.append(nums[q[0]])
# 最后返回 res
return res